home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr48 / pas_0593.zip / SORTQASM.PAS < prev    next >
Pascal/Delphi Source File  |  1993-05-30  |  2KB  |  100 lines
  1. {─ Fido Pascal Conference ────────────────────────────────────────────── PASCAL ─
  2. Msg  : 494 of 527
  3. From : Alexander Christov                  2:341/34.0           14 May 93  12:43
  4. To   : All
  5. Subj : Sorting Routines (3/3)
  6. ────────────────────────────────────────────────────────────────────────────────
  7. Hi All!}
  8.  
  9. { And finally a specific version of QSort() written in Assembler. It is
  10.  non recursive and sorts arrays of WORDs of up to 16383 elements (since
  11.  it uses the addresses of the elements rather than their indexes, and since
  12.  SizeOf(Word)=2 -> 16384*2=32768 "=" -32768, and the routine uses signed
  13.  comparisons between adresses.
  14.   On my 386/33 it sorts 10 times an array of 10000 words in 3.6 sec, while
  15.  the first QSort() does the same in 46 sec.
  16.  
  17.   Must be called with
  18.  
  19.  Qsort(pointer to the first element, 0, elements-1)
  20.  
  21.   Use freely. If you include the source directly in your program, credit
  22.   must be given.
  23. }
  24.  
  25. Procedure QSort(Base:Pointer;L,R:Word);Assembler;
  26. VAR TmpL,TmpR,TmpDI:WORD;
  27. ASM
  28.  XOR AX,AX
  29.  PUSH AX
  30.  PUSH AX     { 0 0 will act as a flag on the stack indicating that no more }
  31.  PUSH R      { (L,R) pairs need to be sorted }
  32.  PUSH L
  33. @MainLoop:
  34.  LES DI,Base
  35.  MOV TmpDI,DI
  36.  XOR SI,SI
  37.  MOV BX,DI
  38.  POP AX    { AX<-L }
  39.  MOV TmpL,AX
  40.  MOV SI,AX
  41.  SHL AX,1
  42.  ADD DI,AX
  43.  POP AX    { AX<-R }
  44.  MOV TmpR,AX
  45.  AND AX,AX     { R can be never 0 except if this is the (0,0) flag }
  46.  JZ @End
  47.  ADD SI,AX
  48.  SHL AX,1
  49.  ADD BX,AX
  50.  AND SI,$FFFE
  51.  ADD SI,TmpDI
  52.  
  53.  { ES:DI -> Element[I] (L)
  54.    ES:BX -> Element[J] (R)
  55.    ES:SI -> Element[(L+R) div 2]
  56.  }
  57.  
  58.  MOV AX,ES:[SI]
  59. @Loop1:
  60.  MOV CX,ES:[DI]
  61.  CMP AX,CX
  62.  JNA @Loop2
  63.  ADD DI,2
  64.  JMP @Loop1
  65. @Loop2:
  66.  MOV CX,ES:[BX]
  67.  CMP CX,AX
  68.  JNA @Check
  69.  SUB BX,2
  70.  JMP @Loop2
  71. @Check:
  72.  CMP DI,BX
  73.  JG @Cont1
  74.  MOV CX,ES:[DI]
  75.  MOV DX,ES:[BX]
  76.  MOV ES:[DI],DX
  77.  MOV ES:[BX],CX
  78.  ADD DI,2
  79.  SUB BX,2
  80.  CMP DI,BX
  81.  JNG @Loop1
  82.  
  83. @Cont1:
  84.  SUB DI,TmpDI
  85.  SAR DI,1       { DI - I }
  86.  SUB BX,TmpDI
  87.  SAR BX,1       { BX - J }
  88.  CMP DI,TmpR
  89.  JGE @Cont2
  90.  PUSH TmpR      { I<R }
  91.  PUSH DI
  92. @Cont2:
  93.  CMP TmpL,BX
  94.  JGE @MainLoop
  95.  PUSH BX        { L<J }
  96.  PUSH TmpL
  97.  JMP @MainLoop
  98.  
  99. @End:
  100. END;